"""
题目描述：使用队列实现栈的下列操作：
push (x) -- 元素x入栈
pop () -- 移除栈顶元素
top () -- 获取栈顶元素
empty () -- 返回栈是否为空。

个人补充：在 Python 中，range 是一个用于生成整数序列的内置函数，主要用于循环场景（如 for 循环），可以高效地生成指定范围的连续整数
range 有三种常用形式：
range(stop)：生成从 0 到 stop-1 的整数（包含 0，不包含 stop）
range(start, stop)：生成从 start 到 stop-1 的整数（包含 start，不包含 stop）
range(start, stop, step)：生成从 start 开始，每次递增 step 的整数，直到小于 stop（step 为步长，可正可负）

核心特点：
    1：惰性计算：range 生成的是一个 “范围对象”（而非直接生成列表），只有在需要时才会计算具体元素，节省内存（尤其对于大范围）。
    r = range(1000000)  # 不占用大量内存
    print(type(r))  # 输出：<class 'range'>

    2：不可变序列：生成的序列不可修改，若需修改可转换为列表：
    lst = list(range(3))  # 转换为 [0, 1, 2]  #注意：一旦转换为list了，就是代表一次性都取出来了 失去了惰性的特点

    3：常用于循环计数：在 for 循环中控制循环次数，替代传统的 “计数变量” 方式，代码更简洁。
总结：
range 的核心作用是生成指定规则的整数序列，尤其适合在循环中控制迭代次数或生成连续/间隔的整数

"""
#是 Python 中导入 collections 模块里 deque 类的语句，用于创建高效的双端队列（double-ended queue）。
#核心作用：
#deque 是一种优化过的数据结构，支持在两端快速添加（append/appendleft）和删除（pop/popleft）元素，时间复杂度均为 O (1)，
# 而普通列表（list）在头部操作（如 pop(0)、insert(0, x)）的时间复杂度是 O (n)，效率较低。

#deque适用场景：
#实现队列（FIFO）：用 append 入队，popleft 出队；
#实现栈（LIFO）：用 append 入栈，pop 出栈；
#滑动窗口、广度优先搜索（BFS）等需要频繁在两端操作元素的场景。
#在算法题中，deque 是处理队列、栈相关问题的高效工具，比普通列表更适合频繁的头部操作。
from collections import deque

class MyStack:
    def __init__(self):
        """初始化一个队列（使用deque实现，因其弹出头部元素效率高） 也体现本题是用队列来实现栈"""
        self.queue = deque()
    #!!!
    def push(self, x: int) -> None:
        #先将元素 x 正常加入队列尾部
        self.queue.append(x)
        # 再把队列中除了刚加入的元素之外的所有旧元素(-1体现了)，依次从队列头部弹出并重新加入队列尾部。以实现栈的先进后出
        for _ in range(len(self.queue) - 1):
            self.queue.append(self.queue.popleft())

    def pop(self) -> int:
        return self.queue.popleft()

    def top(self) -> int:
        return self.queue[0]

    def empty(self) -> bool:
        return len(self.queue) == 0

# 测试示例
obj = MyStack()
obj.push(1)
obj.push(2)
print(obj.top())   # 2
print(obj.pop())   # 2
print(obj.empty()) # False

